#pragma once

#include "WeighGraph.h"
#include <queue>
namespace{
	struct VertexDistance{
		int vertex;
		int distance;
		VertexDistance(int vertex, int distance) : vertex(vertex), distance(distance){}
		VertexDistance(){}
	};

	bool operator < (const VertexDistance& firstStructure, const VertexDistance& secondStructure){
		if (firstStructure.distance > secondStructure.distance)
			return true;
		return false;
	}

	class SimpleDijkstraVisitor{
		std::vector<int> parentsList_;
		std::vector<int> distancesList_;
		std::set<int> visitedVertexes_;
		int vertexNum_;

	public:
		const int INFINITY_DISTANCE_ = 1000000000;
		explicit SimpleDijkstraVisitor(int vertexNum): vertexNum_(vertexNum){
			parentsList_.assign(vertexNum, -1);
		}

		const int weightFunction(const WeighEdge& currentEdge, const std::vector<int>& distances) const{
			return distances[currentEdge.fromVertex] + currentEdge.getWeight();
		}


		void vertexBecomeBlack(int vertex){
			if (!visitedVertexes_.insert(vertex).second){
				throw std::logic_error("Vertex at least two times has become black");
			}
			if (vertex > vertexNum_){
				throw std::out_of_range("Vertex doesn't belong to graph/wrong number of vertex");
			}
		}
		void optionalActionsAtRelaxing(int fromVertex, int toVertex){
			parentsList_[toVertex] = fromVertex;
		}
		void actionAfterAlgorithm(std::vector<int>& distanceList){
			std::swap(distanceList, distancesList_);
		}
		const std::vector<int> getDistances() const{
			return distancesList_;
		}

		std::vector<int> getPathToVertex(int currentVertex){
			std::vector<int> path;
			while (currentVertex != -1){
				path.push_back(currentVertex);
				currentVertex = parentsList_[currentVertex];
			}
			std::reverse(path.begin(), path.end());
			return path;
		}
	};


	template<class T>
	void dijkstraAlgorithmStep(const WeighGraph& G, T* userClass,
		std::priority_queue<VertexDistance>& distanceFromStartToVertexes,
		std::vector<int>& distances){
		VertexDistance stepVertex = distanceFromStartToVertexes.top();
		distanceFromStartToVertexes.pop();
		if (stepVertex.distance > distances[stepVertex.vertex])
			return;
		userClass->vertexBecomeBlack(stepVertex.vertex);
		std::vector<WeightAdjacent> listOfAdjacents = G.getAdjacentWeights(stepVertex.vertex);
		for (auto currentEdge : listOfAdjacents){
			int newDistance = userClass->weightFunction({ stepVertex.vertex, currentEdge.toVertex,
				currentEdge.weight }, distances);
			if (newDistance < distances[currentEdge.toVertex]){
				distances[currentEdge.toVertex] = newDistance;
				distanceFromStartToVertexes.push({ currentEdge.toVertex, newDistance });
				userClass->optionalActionsAtRelaxing(stepVertex.vertex, currentEdge.toVertex);
			}
		}
	}
	
	template<class T>
	void dijkstraAlgorithm(const WeighGraph& G, T* userClass, int startVertex){
		std::vector<int> distances;
		std::priority_queue<VertexDistance> distanceFromStartToVertexes;
		distances.assign(G.getVertexNum(), userClass->INFINITY_DISTANCE_);
		distanceFromStartToVertexes.push({ startVertex, 0});
		distances[startVertex] = 0;
		while (!distanceFromStartToVertexes.empty()){
			dijkstraAlgorithmStep(G, userClass, distanceFromStartToVertexes, distances);
		}
		userClass->actionAfterAlgorithm(distances);
	}

};

